// 一个长度为n的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n之内。
// 在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

var missingNumber: (nums: number[]) => number = function (nums) {
    // 声明左右指针
    let left: number = 0;
    let right: number = nums.length - 1;
    // 二分算法循环，出口需要草稿纸上画一下
    while (left <= right) {
        let mid: number = Math.floor((left + right) / 2);
        // 情况一
        if (nums[mid] === mid) {
            left = mid + 1;
            // 情况二
        } else if (nums[mid] > mid) {
            right = mid - 1;
        }
    }
    return left;
};

        // 排序数组中的搜索问题，首先想到二分搜索算法法解决。
        // 这道题唯一需要想到的就是数组下标和数组下标指向元素之间的关系
        // 最优情况下我们假设数组的数字都是不缺的，那么肯定数组的长度应该是n+1
        // 所以我们用二分法定位到数组中点，中点下标为mid
        // 如果mid = nums[mid]，说明[0, mid]范围内不缺失数字，left 更新为 mid + 1
        // 反之如果mid < nums[mid]，说明[mid, right]范围内不缺失数字，right 更新为 mid - 1
        // 在这道题的情境中mid > nums[mid]这种情况不存在
        // 最后的出口脑子里不好想，但是在纸上画画可以出，我画出来的结论就是返回left指针即可。